UVa/12320 - Flight Control/12320.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <numeric>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 template <class T> string toStr(const T &x) { stringstream s; s << x; return s.str(); }
  24 template <class T> int toInt(const T &x) { stringstream s; s << x; int r; s >> r; return r; }
  25
  26 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  27 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  28 #define D(x) cout << #x " = " << (x) << endl
  29
  30 const double EPS = 1e-10;
  31
  32 int cmp(double x, double y = 0, double tol = EPS){
  33     return( x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  34 }
  35
  36 struct point {
  37     double x, y, z;
  38     point(){} point(double x, double y, double z) : x(x), y(y), z(z) {}
  39 };
  40
  41 int R[2], V[2];
  42 vector< point > P[2];
  43
  44 inline double dist(const point &a, const point &b) {
  45     double dx = b.x - a.x, dy = b.y - a.y, dz = b.z - a.z;
  46     return sqrt(dx * dx + dy * dy + dz * dz);
  47 }
  48
  49 point positionAt(int p, double t) {
  50     double d = V[p] * t, s = 0.0;
  51     for (int i = 0; i < P[p].size() - 1; ++i) {
  52         double distance = dist(P[p][i], P[p][i+1]);
  53         if (cmp(s + distance, d) < 0) {
  54             s += distance;
  55         } else {
  56             point ans = P[p][i];
  57             double dx = P[p][i+1].x - P[p][i].x;
  58             double dy = P[p][i+1].y - P[p][i].y;
  59             double dz = P[p][i+1].z - P[p][i].z;
  60             ans.x += (d - s) * dx / distance;
  61             ans.y += (d - s) * dy / distance;
  62             ans.z += (d - s) * dz / distance;
  63
  64             assert(cmp(s + dist(P[p][i], ans), d) == 0);
  65             return ans;
  66         }
  67     }
  68     assert(false);
  69 }
  70
  71 int main(){
  72     int casos; scanf("%d", &casos); while (casos--) {
  73         for (int p = 0; p < 2; ++p) {
  74             int k; scanf("%d %d %d", &R[p], &V[p], &k);
  75             P[p].resize(k);
  76             for (int i = 0; i < k; ++i) {
  77                 scanf("%lf %lf %lf", &P[p][i].x, &P[p][i].y, &P[p][i].z);
  78             }
  79             P[p].push_back( point(0, 0, 0) );
  80         }
  81
  82         double totalTime = 1e100;
  83         for (int p = 0; p < 2; ++p) {
  84             double d = 0;
  85             for (int i = 0; i < P[p].size() - 1; ++i) {
  86                 d += dist(P[p][i], P[p][i+1]);
  87             }
  88             totalTime = min(totalTime, d / V[p]);
  89         }
  90         //D(totalTime);
  91         int iterations = 9500;
  92         double delta = totalTime / iterations;
  93         // point p1 = positionAt(0, totalTime);
  94         // point p2 = positionAt(1, totalTime);
  95         // printf("<%lf, %lf, %lf>\n", p1.x, p1.y, p1.z);
  96         // printf("<%lf, %lf, %lf>\n", p2.x, p2.y, p2.z);
  97         int ans = 0;
  98         bool outside = true;
  99         for (int i = 0; i <= iterations; ++i) {
 100             double distance = dist(positionAt(0, i * delta), positionAt(1, i * delta));
 101             if (cmp(distance, 1.0 * (R[0] + R[1])) <= 0) {
 102                 if (outside) ans++;
 103                 outside = false;
 104             } else {
 105                 outside = true;
 106             }
 107         }
 108         printf("%d\n", ans);
 109     }
 110     return 0;
 111 }